<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>最长回文子串 - 算法可视化</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", sans-serif;
            background-color: #f8fafc;
            color: #1e293b;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #4f46e5 0%, #7c3aed 50%, #a855f7 100%);
        }
        .code-block {
            background-color: #1e293b;
            border-left: 4px solid #7c3aed;
        }
        .method-card:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 25px -5px rgba(0, 0, 0, 0.1), 0 10px 10px -5px rgba(0, 0, 0, 0.04);
        }
        .highlight {
            position: relative;
        }
        .highlight::after {
            content: '';
            position: absolute;
            bottom: 0;
            left: 0;
            width: 100%;
            height: 30%;
            background-color: rgba(124, 58, 237, 0.2);
            z-index: -1;
            transform: scaleX(1.05);
        }
    </style>
</head>
<body class="min-h-screen">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-6 md:px-16 lg:px-32">
        <div class="max-w-6xl mx-auto">
            <h1 class="text-4xl md:text-5xl lg:text-6xl font-bold mb-6 font-serif">最长<span class="highlight">回文子串</span></h1>
            <p class="text-xl md:text-2xl text-purple-100 mb-8 max-w-3xl">
                探索字符串中最具对称美的秘密 - 两种高效算法解析与可视化
            </p>
            <div class="flex flex-wrap gap-4 mb-8">
                <div class="flex items-center bg-white bg-opacity-10 rounded-full px-4 py-2">
                    <i class="fas fa-clock mr-2"></i>
                    <span>时间复杂度 O(n²)</span>
                </div>
                <div class="flex items-center bg-white bg-opacity-10 rounded-full px-4 py-2">
                    <i class="fas fa-microchip mr-2"></i>
                    <span>空间复杂度 O(1)/O(n²)</span>
                </div>
                <div class="flex items-center bg-white bg-opacity-10 rounded-full px-4 py-2">
                    <i class="fas fa-tags mr-2"></i>
                    <span>动态规划 | 中心扩展</span>
                </div>
            </div>
        </div>
    </section>

    <!-- Problem Definition -->
    <section class="py-16 px-6 md:px-16 lg:px-32 bg-white">
        <div class="max-w-4xl mx-auto">
            <div class="flex items-center mb-8">
                <div class="w-12 h-12 rounded-full bg-purple-100 flex items-center justify-center mr-4">
                    <i class="fas fa-question text-purple-600 text-xl"></i>
                </div>
                <h2 class="text-3xl font-bold text-gray-800 font-serif">问题描述</h2>
            </div>
            <div class="prose prose-lg text-gray-700 max-w-none">
                <p>给定一个字符串 <code class="bg-purple-100 px-2 py-1 rounded">s</code>，找到 <code class="bg-purple-100 px-2 py-1 rounded">s</code> 中最长的回文子串。回文字符串是正着读和反着读都一样的字符串。</p>
                <div class="bg-yellow-50 border-l-4 border-yellow-400 p-4 my-6">
                    <div class="flex">
                        <div class="flex-shrink-0">
                            <i class="fas fa-lightbulb text-yellow-500 mt-1"></i>
                        </div>
                        <div class="ml-3">
                            <p class="text-sm text-yellow-700">
                                <strong>示例：</strong> 输入 <code>"babad"</code>，输出可以是 <code>"bab"</code> 或 <code>"aba"</code>（都是最长的回文子串）。
                            </p>
                        </div>
                    </div>
                </div>
            </div>
        </div>
    </section>

    <!-- Algorithm Comparison -->
    <section class="py-16 px-6 md:px-16 lg:px-32 bg-gray-50">
        <div class="max-w-6xl mx-auto">
            <h2 class="text-3xl font-bold text-gray-800 mb-12 text-center font-serif">算法<span class="text-purple-600">对比</span></h2>
            
            <div class="grid md:grid-cols-2 gap-8">
                <!-- Center Expansion Method -->
                <div class="method-card bg-white rounded-xl shadow-lg overflow-hidden transition-all duration-300">
                    <div class="px-6 py-4">
                        <div class="flex items-center mb-4">
                            <div class="w-10 h-10 rounded-full bg-purple-100 flex items-center justify-center mr-3">
                                <i class="fas fa-expand-alt text-purple-600"></i>
                            </div>
                            <h3 class="text-2xl font-bold text-gray-800">中心扩展法</h3>
                        </div>
                        <div class="prose text-gray-700 mb-4">
                            <p>枚举每个可能的回文中心，尝试向两边扩展，直到无法扩展为止。</p>
                            <ul class="list-disc pl-5">
                                <li>时间复杂度：O(n²)</li>
                                <li>空间复杂度：O(1)</li>
                            </ul>
                        </div>
                    </div>
                    <div class="bg-gray-800 text-gray-100 p-4">
                        <h4 class="text-sm uppercase tracking-wider text-purple-300 mb-3">核心思想</h4>
                        <div class="mermaid">
                            graph LR
                            A[遍历每个字符] --> B[作为奇数中心扩展]
                            A --> C[作为偶数中心扩展]
                            B --> D[记录最长回文]
                            C --> D
                        </div>
                    </div>
                </div>

                <!-- Dynamic Programming Method -->
                <div class="method-card bg-white rounded-xl shadow-lg overflow-hidden transition-all duration-300">
                    <div class="px-6 py-4">
                        <div class="flex items-center mb-4">
                            <div class="w-10 h-10 rounded-full bg-blue-100 flex items-center justify-center mr-3">
                                <i class="fas fa-project-diagram text-blue-600"></i>
                            </div>
                            <h3 class="text-2xl font-bold text-gray-800">动态规划法</h3>
                        </div>
                        <div class="prose text-gray-700 mb-4">
                            <p>定义 dp[i][j] 表示 s[i..j] 是否为回文串，利用已计算的子问题解来构建更大问题的解。</p>
                            <ul class="list-disc pl-5">
                                <li>时间复杂度：O(n²)</li>
                                <li>空间复杂度：O(n²)</li>
                            </ul>
                        </div>
                    </div>
                    <div class="bg-gray-800 text-gray-100 p-4">
                        <h4 class="text-sm uppercase tracking-wider text-blue-300 mb-3">状态转移</h4>
                        <div class="mermaid">
                            graph LR
                            A[s[i] == s[j]] --> B{检查}
                            B -->|j-i<=2| C[dp[i][j]=true]
                            B -->|j-i>2| D[dp[i+1][j-1]?]
                            D --> E[dp[i][j]=true]
                        </div>
                    </div>
                </div>
            </div>
        </div>
    </section>

    <!-- Code Implementation -->
    <section class="py-16 px-6 md:px-16 lg:px-32 bg-white">
        <div class="max-w-6xl mx-auto">
            <h2 class="text-3xl font-bold text-gray-800 mb-12 text-center font-serif">代码<span class="text-purple-600">实现</span></h2>
            
            <div class="grid md:grid-cols-2 gap-8">
                <!-- Center Expansion Code -->
                <div>
                    <div class="flex items-center mb-4">
                        <div class="w-8 h-8 rounded-full bg-purple-100 flex items-center justify-center mr-3">
                            <i class="fas fa-code text-purple-600 text-sm"></i>
                        </div>
                        <h3 class="text-xl font-bold text-gray-800">中心扩展法实现</h3>
                    </div>
                    <div class="code-block rounded-lg overflow-hidden shadow-lg">
                        <div class="flex items-center bg-gray-700 px-4 py-2">
                            <div class="w-3 h-3 rounded-full bg-red-500 mr-2"></div>
                            <div class="w-3 h-3 rounded-full bg-yellow-500 mr-2"></div>
                            <div class="w-3 h-3 rounded-full bg-green-500"></div>
                            <span class="text-gray-300 ml-4 text-sm">LongestPalindrome.java</span>
                        </div>
                        <pre class="text-gray-200 p-4 overflow-x-auto"><code>/**
 * 寻找最长回文子串（中心扩展法）
 * @param s 输入字符串
 * @return 最长回文子串
 */
public String longestPalindrome(String s) {
    if (s == null || s.isEmpty()) return "";
    
    int start = 0, maxLength = 0;
    
    for (int i = 0; i < s.length(); i++) {
        // 奇数长度扩展
        int len1 = expandAroundCenter(s, i, i);
        // 偶数长度扩展
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        
        if (len > maxLength) {
            maxLength = len;
            start = i - (len - 1) / 2;
        }
    }
    
    return s.substring(start, start + maxLength);
}

private int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() 
           && s.charAt(left) == s.charAt(right)) {
        left--; right++;
    }
    return right - left - 1;
}</code></pre>
                    </div>
                </div>

                <!-- Dynamic Programming Code -->
                <div>
                    <div class="flex items-center mb-4">
                        <div class="w-8 h-8 rounded-full bg-blue-100 flex items-center justify-center mr-3">
                            <i class="fas fa-code text-blue-600 text-sm"></i>
                        </div>
                        <h3 class="text-xl font-bold text-gray-800">动态规划法实现</h3>
                    </div>
                    <div class="code-block rounded-lg overflow-hidden shadow-lg">
                        <div class="flex items-center bg-gray-700 px-4 py-2">
                            <div class="w-3 h-3 rounded-full bg-red-500 mr-2"></div>
                            <div class="w-3 h-3 rounded-full bg-yellow-500 mr-2"></div>
                            <div class="w-3 h-3 rounded-full bg-green-500"></div>
                            <span class="text-gray-300 ml-4 text-sm">LongestPalindromeDP.java</span>
                        </div>
                        <pre class="text-gray-200 p-4 overflow-x-auto"><code>/**
 * 寻找最长回文子串（动态规划法）
 * @param s 输入字符串
 * @return 最长回文子串
 */
public String longestPalindromeDp(String s) {
    if (s == null || s.isEmpty()) return "";
    
    int n = s.length();
    int start = 0, maxLength = 1;
    boolean[][] dp = new boolean[n][n];
    
    // 单个字符都是回文
    for (int i = 0; i < n; i++) dp[i][i] = true;
    
    // 检查长度为2的子串
    for (int i = 0; i < n - 1; i++) {
        if (s.charAt(i) == s.charAt(i + 1)) {
            dp[i][i + 1] = true;
            start = i;
            maxLength = 2;
        }
    }
    
    // 检查更长子串
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                start = i;
                maxLength = len;
            }
        }
    }
    
    return s.substring(start, start + maxLength);
}</code></pre>
                    </div>
                </div>
            </div>
        </div>
    </section>

    <!-- Visualization -->
    <section class="py-16 px-6 md:px-16 lg:px-32 bg-gray-50">
        <div class="max-w-6xl mx-auto">
            <h2 class="text-3xl font-bold text-gray-800 mb-12 text-center font-serif">算法<span class="text-purple-600">可视化</span></h2>
            
            <div class="bg-white rounded-xl shadow-lg overflow-hidden">
                <div class="p-6">
                    <div class="flex items-center mb-6">
                        <div class="w-10 h-10 rounded-full bg-purple-100 flex items-center justify-center mr-3">
                            <i class="fas fa-chart-line text-purple-600"></i>
                        </div>
                        <h3 class="text-2xl font-bold text-gray-800">中心扩展法过程演示</h3>
                    </div>
                    
                    <div class="mermaid">
                        %%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#f5f3ff', 'edgeLabelBackground':'#fff'}}}%%
                        journey
                            title 中心扩展法处理 "babad"
                            section 初始化
                                初始字符串: "babad"
                                设置 start=0, maxLength=0
                            section 中心点 i=0 (b)
                                奇数扩展: "b" → len=1
                                偶数扩展: "ba" → 不匹配
                                更新: maxLength=1, start=0
                            section 中心点 i=1 (a)
                                奇数扩展: "a" → "bab" → len=3
                                偶数扩展: "ab" → 不匹配
                                更新: maxLength=3, start=0
                            section 中心点 i=2 (b)
                                奇数扩展: "b" → "aba" → len=3
                                偶数扩展: "ba" → 不匹配
                                保持 maxLength=3
                            section 中心点 i=3 (a)
                                奇数扩展: "a" → len=1
                                偶数扩展: "ad" → 不匹配
                                保持 maxLength=3
                            section 结果
                                最长回文: "bab" 或 "aba"
                    </div>
                </div>
            </div>
        </div>
    </section>

    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'default',
            flowchart: { useMaxWidth: true, htmlLabels: true },
            journey: { useMaxWidth: true, height: 300 }
        });
    </script>
</body>
</html>